package com.interview.javabase.algorithm.动态规划;

import java.util.Arrays;

/**
 * @author www.byteblogs.com
 * @date 2021-10-09
 * @since 2.0
 */
public class 最长公共子序列 {

    public static void main(String[] args) {
        int i = longestCommonSubsequence("122", "22");
        System.out.println(i);
    }

    public static int longestCommonSubsequence(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        char[] n = s1.toCharArray();
        char[] m = s2.toCharArray();
        for (int i = 1; i <= n.length; i++) {
            for (int i1 = 1; i1 <= m.length; i1++) {
                if (n[i -1] == m[i1 -1]) {
                    dp[i][i1] = dp[i - 1][i1 - 1] + 1;
                } else {
                    dp[i][i1] = Math.max(dp[i][i1 - 1], dp[i -1][i1]) ;
                }
            }
        }

        return dp[s1.length()][s2.length()];

    }
}
